package com.rgs.se.algorithm.daywork;

import java.util.HashMap;
import java.util.Map;

/*
 * 两数之和算法     使用哈希表使时间复杂度降低到O(n)
 * */
public class Twosum {
    public static void twosum(int arr[], int num){
        /*创建哈希表*/
        Map<Integer, Integer> ages = new HashMap<Integer, Integer>();
        /*构建哈希表*/
        for (int j = 1; j < arr.length; j++) {
            ages.put(arr[j],j);
        }
        /*遍历数组，在哈希表中找到一个差*/
        for (int i = 0; i < arr.length; i++) {
            int key = num - arr[i];
            if(ages.get(key) != null){
                System.out.println(i+" "+ages.get(key));
                /*防止重复，找到一个后就在哈希表中删除该位置*/
                ages.remove(arr[i]);
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 12, 6, 3, 9, 2, 1, 7};
        System.out.println("结果为");
        twosum(arr, 13);
    }
}
